package Week3;

import java.util.*;

public class Day18 {
}

//牛客:NC101 压缩字符串(一)
class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    public String compressString (String param) {
        // write code here
        StringBuffer ret = new StringBuffer();
        char[] s = param.toCharArray();
        int n = s.length;
        int left = 0 , right = 0;
        while(right < n){
           //遍历相同字符的长度
            while(right < n - 1 && s[right + 1] == s[right]){
                right++;
            }
            //添加字符
            ret.append(s[left]);
            //如果这个字符的个数大于1，就接入它的长度
            if(right - left + 1 > 1){
                ret.append(right - left + 1);
            }
            //更新左区间
            left = right + 1;
            right++;
        }
        return ret.toString();
    }
}

//牛客:chika和蜜柑
class Main15 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() , k = in.nextInt();
        int[][] arr = new int[n][2];
        //将酸度和甜度的值形成一个二维数组
        for(int i = 0; i < n; i++){
            //第0列代表酸度
            arr[i][0] = in.nextInt();
        }
        for(int i = 0; i < n; i++){
            //第1列代表甜度
            arr[i][1] = in.nextInt();
        }
        long sMin = 0;//酸度的总和
        long tMax = 0;//甜度的总和
        //排序
        PriorityQueue<int[]> q = new PriorityQueue<>((x,y) -> {
            //如果甜度相等按照酸度从小到大排序
            if(x[1] == y[1]){
                return x[0] - y[0];
            }else{
                //入不等按照甜度从大到小排序
                return y[1] - x[1];
            }
        });
        //每次放入一组进行排序
        for(int i = 0; i < n; i++){
            q.offer(arr[i]);
        }
        //取排好序的前k个元素，计算总和
        for(int i = 0; i < k; i++){
            int[] tmp = q.poll();
            sMin += tmp[0];
            tMax += tmp[1];
        }
        System.out.println(sMin + " " + tMax);
    }
}

//牛客:NC145 01背包
class Solution3 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[] dp = new int[1010];
        for(int i = 0; i < n; i++){
            for(int j = V; j >= vw[i][0]; j--){
                dp[j] = Math.max(dp[j] , dp[j-vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }
}
